#include <iostream>

int *ComputePrefix(const char *p)
{
  
  int m=strlen(p);
  int *c=new int[m];
  memset(c,0,m*sizeof(int));
  c[0]=0;
  int k=0;
  for(int q=2;q<=m;q++)
    {
      while(k>0&&p[k]!=p[q-1])
	k=c[k-1];
      if(p[k]==p[q-1])
	k=k+1;
      c[q-1]=k;
    }
  return c;
}


void KMP_Matcher(const char *t,const char *p)
{
  int n=strlen(t);
  int m=strlen(p);
  int *c;
  c=ComputePrefix(p);
  int q=0;
  for(int i=1;i<=n;i++)
    {
      while(q>0&&p[q]!=t[i-1])
	q=c[q-1];
      if(p[q]==t[i-1])
	q=q+1;
      if(q==m)
	{
	  printf("Pattern occurs with shift %d\n",i-m+1);
	  q=c[q-1];
        }
    }
}


int main()
{
  KMP_Matcher("dsfdsfsshefgfdgshedsfdfshe","she");
  return 0;
}
